#include <iostream>
#include <stdio.h>
//课时15作业
/*读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，
中序遍历输出3  7 21 34 59 60 80 86 87 99，
针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出2*/

typedef int KeyType;
typedef struct BSTNode
{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

void inset_tree(BiTree &tree, KeyType key)
{
    //申请一个空间
    BiTree newNode=(BiTree)calloc(1,sizeof(BSTNode));
    newNode->key=key;
    //寻找到要插入的位置
    if(NULL == tree){  //判断是否首次插入
        tree=newNode;
        return;
    }
    //tree不为空时
    BiTree temp=tree,parent;
    while(temp != NULL){
        parent=temp;
        if(key < temp->key){ //比根节点小就往左子树插入
            temp=temp->lchild;
        }else if( key > temp->key){  //比根节点大，往右子树插入
            temp=temp->rchild;
        }else{   //相等则不插入
            return;
        }
    }
    if(key < parent->key){
        parent->lchild=newNode;
    }else{
        parent->rchild=newNode;
    }

}
void creat_tree(BiTree &tree)
{
    int num;
    int data[10]={0}; //数组存储需要建树的元素
    int len=sizeof(data)/sizeof(data[0]);
    for(int i=0; i<10; i++)
    {
        scanf("%d",&num);
        data[i]=num;
        inset_tree(tree,data[i]);
    }
}
//中序遍历
void InOrder(BiTree tree)
{
    if(NULL == tree)
    {
        return;
    }
    InOrder(tree->lchild);
    printf("%3d",tree->key);
    InOrder(tree->rchild);
}

//二分查找（折半查找）
int binary_search(int* arr,int len,int key)
{
    int low=0;
    int high=len-1;
    int mid=(low+high)/2;
    while(low<=high){
        if(key > arr[mid]){
            low=mid+1;
            mid=(low+high)/2;
        }
        else if(key < arr[mid]){
            high=mid-1;
            mid=(low+high)/2;
        }
        else{
            return mid;
        }
    }
    return -1;
}

int main() {
    BiTree tree=NULL;
    creat_tree(tree);
    InOrder(tree);
    int arr[]={3, 7, 21, 34, 59, 60, 80, 86, 87, 99};
    int index=binary_search(arr,10,21);
    printf("\n%d",index);
    return 0;
}
